\documentclass[UTF8]{ctexart}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\tikzstyle{startstop} = [rectangle, rounded corners, minimum width=3cm, minimum height=1cm,text centered, draw=black]
\tikzstyle{arrow} = [thick,->,>=stealth]
%流程图排版
\usepackage{xltxtra}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}
%图片排版

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}  
%\usepackage{algorithm}  
%\usepackage{algorithmicx}  
%\usepackage{algpseudocode}  
\usepackage{amsmath}

\title{二叉树和节点的逻辑设计}
\author{陈乐瑶\\ 信息与计算科学\quad 3210103710}
\date{\today}
\begin{document}
\maketitle
\pagestyle{plain}

\section{设计思路}
设计两个基类，BinaryTree和Node。
\begin{enumerate}
\item BinaryTree作为一般的二叉树类型，包含了二叉树的基本成员和函数，如构造函数、输出函数等，其中insert()和remove()为纯虚函数，在不同的二叉树中有不同的实现。
\item Node作为一般的节点类型，是二叉树共有的成员类型，包含了节点的基本成员和函数，如元素值、指向左右节点的指针以及操作元素的函数。
\end{enumerate}

\subsection{二叉树的逻辑设计}

\begin{center}
\begin{tikzpicture}[node distance=1.5cm]
  \node (main) [startstop] {BinaryTree};
  \node (sub1) [startstop,left of=main,xshift=-4cm,yshift=-2.5cm]{BinarySearchTree};
  \node (sub2) [startstop,below of=main,yshift=-1cm]{AVLTree};
  \node (sub3) [startstop,right of=main,xshift=4cm,yshift=-2.5cm]{SplayTree};

  \draw [arrow] (main) -- (sub2);
  \draw [arrow] (main) -| (sub1);
  \draw [arrow] (main) -| (sub3);
\end{tikzpicture}
\end{center}
我们以BinarySearchTree,AVLTree和SplayTree为例作为BinaryTree的继承类。

在BinaryTree的public中写二叉树共有函数的接口，在private中写这些函数的实现。其中，纯虚函数insert()和remove()只需要在public下写virtual的接口，其具体实现写在具体二叉树的private下，如AVLTree中就需要在它的插入删除函数中加入balance()这一步骤。

需要注意的是，根据不同二叉树的特性，我们需要写其特有的成员和函数，如AVLTree需要写常量ALLOWED\_IMBALANCE以及balance(), rotateWithLeftChild()等函数，SplayTree需要写节点nullNode以及reclaimMemory(), rotateWithLeftChild()等函数。

\subsection{节点的逻辑设计}

\begin{center}
\begin{tikzpicture}[node distance=1.5cm]
  \node (main) [startstop] {Node};
  \node (sub1) [startstop,left of=main,xshift=-4cm,yshift=-2.5cm]{BSTNode};
  \node (sub2) [startstop,below of=main,yshift=-1cm]{AVLNode};
  \node (sub3) [startstop,right of=main,xshift=4cm,yshift=-2.5cm]{SplayNode};

  \draw [arrow] (main) -- (sub2);
  \draw [arrow] (main) -| (sub1);
  \draw [arrow] (main) -| (sub3);
\end{tikzpicture}
\end{center}
根据设置的三个继承二叉树，我们也就有三个不同的节点继承类：BSTNode,AVLNode,SplayNode。同样地，我们根据不同二叉树的特性需要，在AVLNode中加入成员height。

（由于技术限制下面给出一个使用线上做图软件的UML图：）
\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.8\textwidth]{fig2.png}
  \caption{类的设计}
\end{figure}

\end{document}
